package leetcode.top100.Code39_40组合问题;

import java.util.*;

/**
 * 给定一个数组 candidates 和一个目标数 target ，
 * 找出 candidates 中所有可以使数字和为 target 的组合。
 * <p>
 * candidates 中的每个数字在每个组合中只能使用一次。
 * <p>
 * 说明：
 * <p>
 * 所有数字（包括目标数）都是正整数。
 * 解集不能包含重复的组合。 
 * 示例 1:
 * <p>
 * 输入: candidates = [10,1,2,7,6,1,5], target = 8,
 * 所求解集为:
 * [
 * [1, 7],
 * [1, 2, 5],
 * [2, 6],
 * [1, 1, 6]
 * ]
 * 示例 2:
 * <p>
 * 输入: candidates = [2,5,2,1,2], target = 5,
 * 所求解集为:
 * [
 *   [1,2,2],
 *   [5]
 * ]
 * <p>
 * 这题同{@link Code39_组合总和_目标和}不一样的地方有2：
 * <p>
 * 1：不可以重复使用元素
 * <p>
 * 2：不能有重复的组合
 * <p>
 *  这题不能用背包问题来看待。要基于{@link Code39_组合总和_目标和}
 * @since 2019/11/26 0026 下午 10:58
 */
public class Code40_组合总和_目标和2 {
    //方式1：回溯
    public static List<List<Integer>> combinationSum1(int[] candidates, int target) {
        if (candidates == null || candidates.length == 0) return new LinkedList<>();
        List<List<Integer>> res = new LinkedList<>();
        Stack<Integer> stack = new Stack<>();
        //注意这里，必须要先排序。{2,3,4,2,7} -> {2,2,3,4,7}去重时候方便
        Arrays.sort(candidates);
        process1(candidates, target, 0, stack, res);
        return res;
    }

    private static void process1(int[] candidates, int target, int index,  Stack<Integer> stack,
                                 List<List<Integer>> res) {
        if (target == 0) {
            res.add(new ArrayList<>(stack));
            return;
        }
        if (target < 0 || index >= candidates.length) return;

        //从当前i位置开始，只往后看。并且{2,2,2,3,4,5} 中第2和第3个2都要跳过。
        for (int i = index; i < candidates.length; i++) {
            //如果这里对index判断会出现问题。{2,2,3,6,7}中，
            // 第一个取2，然后第二个2判断和第一个2等就跳过，跳过了{2,2,3}答案
//            if(index > 0 && candidates[index] == candidates[index -1]){

            //这里要对i进行判断。又如{2,2,2,3,6,7}
            // 第一个2是允许其自由组合的。当以第一个2为基准的排完后得到{2,2,3}
            //第二个2要跳过，因为会产生重复。同样第三个2也要跳过。
            //第2个2和第3个2的场景，都在第一个2子递归中出现过。
            if(i > index && candidates[i] == candidates[i-1]){
                continue;
            }
            stack.push(candidates[i]);
            //不可重复使用当前元素，那么就是从i+1开始。
            process1(candidates, target - candidates[i], i+1, stack, res);
            stack.pop();
        }
    }

    public static void main(String[] args) {
        int[] arr = {2, 2, 3, 6, 7};
        combinationSum1(arr, 7).forEach(System.out::println);
    }
}
